import java.util.*;

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Partition {
    public ListNode partition(ListNode pHead, int x) {
        ListNode bs=null;
        ListNode be=null;
        ListNode as=null;
        ListNode ae=null;

        ListNode cur=pHead;
        while(cur!=null){
            if(cur.val<x){
                //第一次插入
                if(bs==null){
                    bs=be=cur;
                }else{
                    be.next=cur;
                    be=cur;//或be=be.next;
                }
            }else{
                if(as==null){
                    as=ae=cur;
                }else{
                    ae.next=cur;
                    ae=cur;//或ae=ae.next;
                }
            }
            cur=cur.next;
        }
        //第一个段没有数据
        if(bs==null)
            return as;
        be.next=as;
        //防止最大的数据不是最后一个
        if(ae!=null)
            ae.next=null;
        return bs;
    }
}
